﻿// poj3662 Telephone Lines.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*

http://poj.org/problem?id=3662

电话线
时间限制：1000MS 内存限制：65536K
总提交量。13751份 已接受。4838
描述

农场主约翰想在他的农场里架设一条电话线。不幸的是，电话公司并不合作，所以他需要支付一些将他的农场连接到电话系统所需的电缆。

有N（1≤N≤1,000）根编号为1...N的荒废的电线杆散布在农民约翰的地产周围；没有电缆连接任何它们。总共有P（1≤P≤10,000）对电线可以用电缆连接；
其余的都相距太远。

第i条电缆可以连接两个不同的极点Ai和Bi，如果使用的话，长度为Li（1≤Li≤1,000,000）单位。
输入的数据集从未对任何{Ai, Bi}对命名超过一次。杆1已经连接到电话系统，杆N在农场。1号杆和N号杆需要通过电缆的路径连接；
其余的杆子可能被使用，也可能不被使用。

结果是，电话公司愿意为农民约翰免费提供K（0≤K<N）长度的电缆。除此之外，他将不得不支付相当于他所需要的最长的剩余电缆的长度（每对电线杆用单独的电缆连接），
如果他不需要任何额外的电缆，则价格为0。

确定农夫约翰必须支付的最低金额。

输入

*第1行。三个隔开空间的整数。N, P, 和 K
* 第2行...P+1。第i+1行包含三个隔开空间的整数。Ai, Bi, and Li

输出

* 第1行。一个整数，农民约翰可以支付的最低金额。如果不可能将农场与电话公司连接起来，则打印-1。

输入样本

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输出样本

4
*/
int main()
{
    std::cout << "Hello World!\n";
}
 